package traverser;

/**
 * ParentTrackQueue.java
 * 
 * Extension of Queue.java, designed to track the order pages are seen in.
 * Uses a pair of parallel arrays.
 * 
 * Author: Dan Roberts
 * Last Modified: 10/10/11
 */

public class ParentTrackQueue<Item> extends Queue<Item> {
	String [] parent;
	int [] childCount;
	int headParent;  // the parent of the earliest entry (close to pop)
	int tailParent;  // the parent of the latest entry (close to push)
	
	public ParentTrackQueue () {
		super();
		parent = new String[5];
		childCount = new int[5];
		tailParent = -1;
		headParent = 0;
		
	}
	
	public void push (Item value) {
		//System.out.println("Push " +value + " ---- parent " + parent[tailParent]);
		super.push(value);
		childCount[tailParent]++;
	}
	
	public Item pop () {
		childCount[headParent]--;
		if (childCount[headParent] <= 0) {
			headParent++;
		}
		if (headParent > tailParent) {
			// Apparently this error doesn't matter...?
			System.err.println("Popped more than we pushed!");
		}
		Item value = super.pop();
		//System.out.println("Pop " + value + " ---- parent " + parent[headParent]);
		return value;
	}
	
	// Adds a new parent to the list of parents.
	public void addParent (String word) {
		tailParent++;
		if (tailParent >= parent.length	) {
			String [] ptemp = new String[parent.length * 2];
			int [] ctemp  = new int [childCount.length * 2];
			for (int i = 0; i < parent.length; i++) {
				ptemp[i] = parent[i];
				ctemp[i] = childCount[i];
			}
			parent = ptemp;
			childCount = ctemp;
		}
		
		parent[tailParent] = word;
		childCount[tailParent] = 0;
	}
	
	public String currentParent () {
		return parent[headParent];
	}
	
	
	
	public static void main (String [] args) {
		ParentTrackQueue<Integer> test = new ParentTrackQueue<Integer>();
		test.addParent("p1");
		System.out.println(test.currentParent());
		test.push(1);
		test.push(2);
		test.push(3);
		test.addParent("p2");
		test.push(4);
		test.push(5);
		System.out.println(test.currentParent());
		System.out.println(test.pop() + "\n");
		System.out.println(test.currentParent());
		test.push(6);
		test.printReverse();
		System.out.println();
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.currentParent());
		
		test.addParent("p3");
		
		test.push(7);
		test.addParent("p4");
		test.push(8);
		test.addParent("p5");
		test.push(9);
		test.addParent("p6");
		test.push(10);
		
		System.out.println(test.currentParent());
		
		test.print();
		
		System.out.println();
		
		System.out.println(test.pop());
		System.out.println(test.pop());
		
		test.push(11);
		
		System.out.println();
		
		test.print();
		
		System.out.println();
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.currentParent());
		
		System.out.println();
		test.print();
		
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.currentParent());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.pop());
		System.out.println(test.currentParent());
	}
}
